package leetcode_day._2021._202110;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/10/27 9:06
 * 删除无效的括号
 * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 * 返回所有可能的结果。答案可以按 任意顺序 返回。
 * 算法：深度优先搜索
 * 判断删除的最小数量是多少
 * 把对字符串的合法判断转化为 [数学判定]
 */
public class _27_301 {
    int n, len, max;
    String s;
    Set<String> set = new HashSet<>();

    public List<String> removeInvalidParentheses(String s) {
        this.s = s;
        n = s.length();
        // l 表示需要删除的左括号的个数，r 表示需要删除的右括号的个数
        int l = 0, r = 0;
        int c1 = 0, c2 = 0;
        // ()()))
        for (char c : s.toCharArray()) {
            if (c == '(') {
                ++l;
                ++c1;
            } else if (c == ')'){
                ++c2;
                if (l > 0) --l;
                else ++r;
            }
        }
        // len 表示去掉最少数量后，最终合法字符的长度
        len = n - l - r;
        // max 表示左右括号的最大数量
        max = Math.min(c1, c2);
        dfs(0, "", l, r, 0);
        return new ArrayList<>(set);
    }
    // score 用来判断字符串 [是否合法]
    void dfs(int u, String cur, int l, int r, int score) {
        if (l < 0 || r < 0 || score < 0 || score > max) return;
        if (l == 0 && r == 0 && cur.length() == len) set.add(cur);
        if (u == n) return;
        char c = s.charAt(u);
        if (c == '(') {
            // 要么加，要么不加
            dfs(u + 1, cur + c, l, r, score + 1);
            dfs(u + 1, cur, l - 1, r, score);
        } else if (c == ')') {
            dfs(u + 1, cur + c, l, r, score - 1);
            dfs(u + 1, cur, l, r - 1, score);
        } else dfs(u + 1, cur + c, l, r, score);
    }

}
